﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Xml;

using HeapModel.ProgInfo;
using HeapModel.ConcreteMemory;
using System.Diagnostics.Contracts;
using System.IO;

namespace HeapModel.RegionPartition
{
	/// <summary>
	/// Class representing heap (summary) regions.
	/// </summary>
	public sealed class RegionNode
	{
		////////////////////////////////////////////////////////////////////////////
		//Member fields that are useful for both child classes

		//simple id for this region, it can change
		private int m_regionid; 

		//internal conn stuff
		private List<ConcreteNode> m_contnodes;
		private HashSet<TypeIdentifier> m_types;

		public ExtraNodeFacts ExtraFacts;

		//shadow node info
		internal GraphColor NodeColor;
		internal short TimeDiscover;
		internal short TimeFinish;

		internal static short DFSTimeCtr;

		////////////////////////////////////////////////////////////////////////////
		//Basic Operations

		/// <summary>
		/// Create a heap region without setting any of the fields.
		/// </summary>
		private RegionNode(int rid)
		{
			this.m_regionid = rid;

			this.m_contnodes = null;
			this.m_types = null;

			this.NodeColor = GraphColor.White;
		}

		/// <summary>
		/// Create a heap region initialized as needed with the info from the given ConcreteObject.
		/// </summary>
		internal static RegionNode InitRegionFromSingleConcreteObj(ConcreteNode inode)
		{
			Contract.Requires(inode != null);
			Contract.Ensures(Contract.Result<RegionNode>() != null);

			RegionNode hr = new RegionNode(inode.ConcreteNodeID);
			hr.m_contnodes = new List<ConcreteNode>();
			hr.m_contnodes.Add(inode);
			hr.m_types = new HashSet<TypeIdentifier>();
			hr.m_types.Add(inode.ConcreteNodeType);

			return hr;
		}

		/// <summary>
		/// Use this when joining or to pretty up edge id (so we don't have huge and confusing id numbers).
		/// </summary>
		internal void UpdateRegionID(int newid)
		{ this.m_regionid = newid; }

		////////////////////////////////////////////////////////////////////////////
		//Query Methods

		public int RegionID 
		{ get { return this.m_regionid; } }
		
		public HashSet<TypeIdentifier> RegionTypes 
		{ get { return this.m_types; } }

		public List<ConcreteNode> ConcreteNodeList
		{ get { return this.m_contnodes; } }

		/// <summary>
		/// Efficient (well better than the really naieve way) set manipulation BUT may modify either argument.
		/// </summary>
		private static List<ConcreteNode> ConcreteListsAppend(List<ConcreteNode> l1, List<ConcreteNode> l2)
		{
			Contract.Requires(l1 != null);
			Contract.Requires(l2 != null);
			Contract.Ensures(Contract.Result<List<ConcreteNode>>() != null);

			List<ConcreteNode> cnl = new List<ConcreteNode>(l1.Count + l2.Count);
			cnl.AddRange(l1);
			cnl.AddRange(l2);

			return cnl;
		}

		/// <summary>
		/// Join all the heap equivalence classes into a new summary set, potentially mangle objects in the set (you should remove them after this).
		/// </summary>
		internal static RegionNode JoinRegionEqClasses(ICollection<RegionNode> toMerge)
		{
			Contract.Requires(toMerge != null);
			Contract.Requires(toMerge.Count >= 2);
			
			Contract.Ensures(Contract.Result<RegionNode>() != null);

			HashSet<TypeIdentifier> rgntypes = new HashSet<TypeIdentifier>();
			List<ConcreteNode> rgnnodes = new List<ConcreteNode>();
			
			int minid = Int32.MaxValue;
			foreach(RegionNode hr in toMerge)
			{
				minid = Math.Min(minid, hr.m_regionid);
				rgntypes.UnionWith(hr.m_types);
				rgnnodes = ConcreteListsAppend(rgnnodes, hr.m_contnodes);
			}

			RegionNode res = new RegionNode(minid);
			res.m_types = rgntypes;
			res.m_contnodes = rgnnodes;

			return res;
		}

		////////////////////////////////////////////////////////////////////////////
		//Query for display

		public override String ToString()
		{
			bool first;
			StringBuilder sb = new StringBuilder("(" + this.m_regionid);

			sb.Append(", types={");
			first = true;
			foreach(TypeIdentifier tt in this.m_types)
			{
				if(first)
					first = false;
				else
					sb.Append(", ");
				sb.Append(tt);
			}
			sb.Append("}");
			sb.Append(")");
			return sb.ToString();
		}

		/// <summary>
		/// Dump the node (which we know is a home location for some variable or static) as a nice dgml construct into the given xmlwriter.
		/// </summary>
		/// <param name="nodes">The xmlwriter that we write into.</param>
		internal void WriteDgmlForRootNode(String name, bool isstatic, XmlWriter nodes)
		{
			Contract.Requires(!String.IsNullOrEmpty(name));

			nodes.WriteStartElement("Node");
			nodes.WriteAttributeString("Id", name);

			nodes.WriteAttributeString("Label", name);
			
			nodes.WriteAttributeString("SizeInBytes", DgmlExtensions.FormatByteTotal(4));
			nodes.WriteAttributeString("ObjectCount", 1.ToString());

			nodes.WriteAttributeString("OnlyReachFromStatic", isstatic.ToString());
			nodes.WriteAttributeString("NullNode", false.ToString());
			
			nodes.WriteAttributeString("HeapPercent", 0.ToString());

			if(isstatic)
			{
				nodes.WriteAttributeString("Background", "Gold");
				nodes.WriteAttributeString("Category", "LocalRoot");
			}
			else
			{
				nodes.WriteAttributeString("Background", "Turquoise");
				nodes.WriteAttributeString("Category", "StaticRoot");
			}

			nodes.WriteEndElement();
		}

		/// <summary>
		/// Dump the node as a nice dgml construct into the given xmlwriter.
		/// </summary>
		internal void WriteDgmlForRegularNode(XmlWriter nodes)
		{
			Contract.Requires(nodes != null);

			bool first;
			nodes.WriteStartElement("Node");
            nodes.WriteAttributeString("Id", this.m_regionid.ToString());

			nodes.WriteStartAttribute("Label");

			//nodes.WriteString("$" + this.m_regionid.ToString() + " ");

			List<TypeIdentifier> idtl = new List<TypeIdentifier>(this.m_types);
			idtl.Sort((TypeIdentifier tid1, TypeIdentifier tid2) => tid1.NameValue.CompareTo(tid2.NameValue));

			nodes.WriteString("{");
			int ctr = 0;
			foreach(TypeIdentifier tt in idtl)
			{
				if(ctr != 0)
					nodes.WriteString(", ");
				++ctr;
				nodes.WriteString(tt.NameValue);

				if(ctr >= 3)
				{
					nodes.WriteString(", ...");
					break;
				}
			}
			nodes.WriteString("}");

			if(this.ExtraFacts.Shape != RegionShapeEnum.Atomic)
				nodes.WriteString(", " + this.ExtraFacts.Shape.ToString());

			nodes.WriteEndAttribute();

			if(this.ExtraFacts.ContainerCount != 0)
			{
				StringBuilder cardsb = new StringBuilder("|C|=");
				if(this.ExtraFacts.MinContainer == this.ExtraFacts.MaxContainer)
					cardsb.Append(this.ExtraFacts.MinContainer.ToString());
				else
					cardsb.Append("[" + this.ExtraFacts.MinContainer.ToString() + ", " + this.ExtraFacts.MaxContainer.ToString() + "]");

				nodes.WriteAttributeString("Cardinality", cardsb.ToString());
			}

			nodes.WriteAttributeString("ObjectCount", this.m_contnodes.Count.ToString());
			nodes.WriteAttributeString("SizeInBytes", DgmlExtensions.FormatByteTotal(this.ExtraFacts.TotalDataBytes + this.ExtraFacts.TotalOverheadBytes));
			nodes.WriteAttributeString("HeapPercent", ((int)(100 * this.ExtraFacts.HeapPercent)).ToString());

			nodes.WriteAttributeString("OnlyReachFromStatic", this.ExtraFacts.NotReachFromLocal.ToString());
			nodes.WriteAttributeString("DataRatio", this.ExtraFacts.DataToGlueRatio.ToString());

			nodes.WriteStartAttribute("Types");
			first = true;
			foreach(TypeIdentifier tt in idtl)
			{
				if(first)
					first = false;
				else
					nodes.WriteString(" ");
				nodes.WriteString(tt.NameValue);
			}
			nodes.WriteEndAttribute();

			nodes.WriteStartAttribute("WitnessAddress");
			nodes.WriteString("0x" + this.ConcreteNodeList.Min((ConcreteNode cn) => cn.ConcreteNodeID).ToString("x"));
			nodes.WriteEndAttribute();

			if(!this.m_types.Any((TypeIdentifier tt) => tt.IsSpecialNullType))
				nodes.WriteAttributeString("Category", "Atom");
			else
			{
				nodes.WriteAttributeString("NullNode", true.ToString());
				nodes.WriteAttributeString("Category", "ExplicitNull");
				nodes.WriteAttributeString("Background", "Brown");
			}
			
			nodes.WriteEndElement();
		}

		/// <summary>
		/// Compute the total number of bytes in this.
		/// </summary>
		internal int ComputeTotalBytes()
		{
			int totalbytes = 0;
			foreach(ConcreteNode n in this.m_contnodes)
				totalbytes += (n.DataSizeInBytes + n.GlueSizeInBytes);
			return totalbytes;
		}

		/// <summary>
		/// Compute the info we need later when displaying this node in a graph.
		/// </summary>
		internal void ComputeNodeInfo(bool isreachfromlocal, int totalheapbytes, HashSet<ConcreteNode> rgnrootset)
		{
			this.ExtraFacts = new ExtraNodeFacts(isreachfromlocal);

			foreach(ConcreteNode cn in this.ConcreteNodeList)
			{
				this.ExtraFacts.TotalDataBytes += cn.DataSizeInBytes;
				this.ExtraFacts.TotalOverheadBytes += cn.GlueSizeInBytes;

				if(cn.ConcreteNodeType.IsCollectionType)
				{
					this.ExtraFacts.ContainerCount++;
					
					this.ExtraFacts.MinContainer = Math.Min(cn.ContainerSizeInfo, this.ExtraFacts.MinContainer);
					this.ExtraFacts.MaxContainer = Math.Max(cn.ContainerSizeInfo, this.ExtraFacts.MaxContainer);
				}
			}

			this.ExtraFacts.DataToGlueRatio = (this.ExtraFacts.TotalOverheadBytes != 0) ? ((float)this.ExtraFacts.TotalDataBytes) / ((float)this.ExtraFacts.TotalOverheadBytes) : -1.0f;
			
			this.ExtraFacts.HeapPercent = ((float)(this.ExtraFacts.TotalDataBytes + this.ExtraFacts.TotalOverheadBytes)) / ((float)totalheapbytes);

			//////
			//Experiment with structure identification
			HashSet<AccessPath> internalpaths = new HashSet<AccessPath>();
			this.ExtraFacts.Shape = this.ComputeNodeShape(rgnrootset, internalpaths);
			this.ExtraFacts.InternalPaths.AddRange(internalpaths);
		}

		/// <summary>
		/// Compute the shape of the region node.
		/// </summary>
		internal RegionShapeEnum ComputeNodeShape(HashSet<ConcreteNode> rgnroots, HashSet<AccessPath> internalpaths)
		{
			HashSet<AccessPath> treefields = new HashSet<AccessPath>();
			HashSet<AccessPath> crossfields = new HashSet<AccessPath>();
			HashSet<AccessPath> backfields = new HashSet<AccessPath>();

			Dictionary<ConcreteNode, int> colormap = new Dictionary<ConcreteNode, int>();
			foreach(ConcreteNode cn in this.m_contnodes)
				colormap.Add(cn, 0);

			List<ConcreteNode> cnl = new List<ConcreteNode>(rgnroots);
			cnl.Sort((ConcreteNode cn1, ConcreteNode cn2) => cn1.ConcreteNodeType.ToString().CompareTo(cn2.ConcreteNodeType.ToString()));

			bool selfptr = false;
			foreach(ConcreteNode cn in cnl)
				this.NodeShapeDFSHelper(cn, colormap, treefields, crossfields, backfields, ref selfptr);

			internalpaths.UnionWith(treefields);
			internalpaths.UnionWith(crossfields);
			internalpaths.UnionWith(backfields);

			if(backfields.Count == 0)
			{
				if(treefields.Count == 0 && crossfields.Count == 0)
					return RegionShapeEnum.Atomic;
				else if(crossfields.Count != 0)
					return RegionShapeEnum.Dag;
				else
				{
					if(treefields.Count == 1)
						return RegionShapeEnum.List;
					else
						return RegionShapeEnum.Tree;
				}
			}
			else
			{
				return RegionShapeEnum.Cycle;
			}
		}

		private void NodeShapeDFSHelper(ConcreteNode cn, Dictionary<ConcreteNode, int> colormap, HashSet<AccessPath> treefields, HashSet<AccessPath> crossfields, HashSet<AccessPath> backfields, ref bool selfptr)
		{
			colormap[cn] = 1; //grey

			List<ConcretePointer> cpl = new List<ConcretePointer>(cn.PointerTargets);
			cpl.Sort((ConcretePointer cp1, ConcretePointer cp2) => cp1.LocationInSource.ToString().CompareTo(cp2.LocationInSource.ToString()));

			foreach(ConcretePointer cp in cpl)
			{
				if(!colormap.ContainsKey(cp.Target))
					continue; //in another region so we don't care

				ConcreteNode tn = cp.Target;

				if(tn == cn)
					selfptr = true;

				if(colormap[tn] != 0)
				{
					//!white
					if(colormap[tn] == 1)
						backfields.Add(cp.LocationInSource);
					else
						crossfields.Add(cp.LocationInSource);
				}
				else
				{
					treefields.Add(cp.LocationInSource);

					this.NodeShapeDFSHelper(cp.Target, colormap, treefields, crossfields, backfields, ref selfptr);
				}
			}

			colormap[cn] = 2; //black
		}
	}

	public enum RegionShapeEnum
	{
		Atomic,
		List,
		Tree,
		Dag,
		Cycle
	}

	public sealed class ExtraNodeFacts
	{
		internal bool NotReachFromLocal;

		internal int TotalDataBytes;
		internal int TotalOverheadBytes;
		internal float HeapPercent;

		internal int ContainerCount;
		internal int MinContainer;
		internal int MaxContainer;
		
		internal float DataToGlueRatio;

		public readonly List<AccessPath> InternalPaths;
		public RegionShapeEnum Shape;

		internal ExtraNodeFacts(bool notreachfromlocal)
		{
			this.NotReachFromLocal = notreachfromlocal;
			this.TotalDataBytes = 0;
			this.TotalOverheadBytes = 0;

			this.ContainerCount = 0;
			this.MinContainer = Int32.MaxValue;
			this.MaxContainer = Int32.MinValue;
			
			this.DataToGlueRatio = -1.0f;

			this.InternalPaths = new List<AccessPath>();
			this.Shape = RegionShapeEnum.Atomic;
		}
	}
}
